#include <stdio.h>
#include <malloc.h>

#define MAX_SIZE 100

typedef struct
{
    char data[MAX_SIZE]; 
    int length; 
}SqString; 


static void str_assign(SqString &s, char cstr[])
{
    int i;
    for(i = 0; cstr[i] != '\0'; i++)
        s.data[i] = cstr[i];
    s.length = i;
}

static void destroy_str(SqString &s)
{

}


static void disp_str(SqString s)
{
    int i;

    if(s.length > 0)
    {
        for(i = 0; i < s.length; i++)
            printf("%c", s.data[i]);
        printf("\n");
    }
}


static void get_next(SqString t, int next[])
{
    int j = 0, k = -1;

    next[0] = -1;
    while(j < t.length - 1)
    {
        if(k == -1 || t.data[j] == t.data[k]) 
        {
            j++;
            k++;
            next[j] = k;
        }
        else
            k = next[k];
    }
}

static void display(SqString s, SqString t, int i, int j)
{
    int k;
    printf("  ");
    for(k = 0; k < i; k++)
        printf("  ");
    printf("↓ i = %d, j = %d\n", i, j);
    printf("s:");
    for(k = 0; k < s.length; k++)
        printf("%c ", s.data[k]);
    printf("\n");
    printf("t:");
    for(k = 0; k < i - j; k++) 
        printf("  ");
    for(k = 0; k < t.length; k++) 
        printf("%c ", t.data[k]);
    printf("\n");
    for(k = 0; k < i - j; k++) 
        printf("  ");
    for(k = 0; k <= j; k++) 
        printf("  ");
    printf("↑\n"); 
}

static int count_times(SqString s, SqString t)
{
    int i = 0, j = 0;
    int times = 0; 
    int next[MAX_SIZE];

    get_next(t, next);
    display(s, t, i, j);
    while(i < s.length && j < t.length)
    {
        if((j == -1) || (s.data[i] == t.data[j]))
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
            display(s, t, i, j);
        }
        if(j == t.length)
        {
            display(s, t, i, j);
            printf("\t成功匹配1次\n");
            times++;
            j = 0; 
        }
    }

    return times;
}

int main(int argc, char *argv[])
{
    SqString s, t;

    str_assign(s, "aaabbdaabbde");
    str_assign(t, "aabbd");
    printf("t在s中出现的次数:%d\n", count_times(s, t));
    destroy_str(s);
    destroy_str(t);

    return 0;
}
